﻿using Common;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AlgorithmCenter
{
    public class AlgorithmCenter200903
    {
        private int[,] _Remember;
        public int PackageOf0_1(int weight,int[] goodsWeight,int[] goodsValue)
        {
            _Remember = new int[goodsWeight.Length+1, weight+1];
            _Remember.InitToSameValue(-1);
            SolvePackageOf0_1ByDfs(0, weight, goodsWeight, goodsValue);
            return SolvePackageOf0_1ByDp(weight, goodsWeight, goodsValue);
        }

        //深度搜索+记忆化
        private int SolvePackageOf0_1ByDfs(int goodIndex,int remainingWeight, int[] goodsWeight, int[] goodsValue)
        {
            //存在记忆 则直接返回  不需要计算
            if (_Remember[goodIndex, remainingWeight] >= 0)
                return _Remember[goodIndex, remainingWeight];

            int res;
            if (goodIndex >= goodsWeight.Length)
                res = 0;
            else if (remainingWeight < goodsWeight[goodIndex])
                res= SolvePackageOf0_1ByDfs(goodIndex + 1, remainingWeight, goodsWeight, goodsValue);
            else
                res=Math.Max(SolvePackageOf0_1ByDfs(goodIndex + 1, remainingWeight - goodsWeight[goodIndex], goodsWeight, goodsValue) + goodsValue[goodIndex],
                             SolvePackageOf0_1ByDfs(goodIndex + 1, remainingWeight, goodsWeight, goodsValue));

            //增加记忆
            _Remember[goodIndex, remainingWeight] = res;

            return res;
        }

        /// <summary>
        /// dp方程：从前i个物品中选出总重不超过j的物品的价值最大值(注：注意这种范围型的状态，前边的所有状态都已经计算过)
        /// dp[0,w]=0
        /// dp[i,w]=max{dp[i-1,w],dp[i-1,w-w[i]]+v[i]}  (w>=w[i])
        /// dp[i,w]=dp[i-1,w]  (w<w[i])
        /// </summary>
        /// <param name="weight"></param>
        /// <param name="goodsWeight"></param>
        /// <param name="goodsValue"></param>
        /// <returns></returns>
        private int SolvePackageOf0_1ByDp(int weight, int[] goodsWeight, int[] goodsValue)
        {
            int[,] dp = new int[goodsWeight.Length+1,weight+1];            
            //当i等于0时表示从前0个物品中选出总重不超过j的最大价值，显然肯定都是0
            for (int w=0;w<=weight;w++)
            {
                dp[0, w] = 0;
            }

            for (int i = 1; i <= goodsWeight.Length; i++)
            {
                for (int w=0;w<=weight;w++)
                {
                    //如果当前剩余容量小于第i个物品质量，那么前i个物品的价值最大值等于前i-1个物品的价值最大值
                    if (w < goodsWeight[i - 1])
                    {
                        dp[i, w] = dp[i - 1, w];
                    }
                    else
                    {
                        dp[i, w] = Math.Max(dp[i-1,w],dp[i-1,w-goodsWeight[i-1]]+goodsValue[i-1]);
                    }
                }
            }

            return dp[goodsWeight.Length,weight];
        }
    }
}
